Ranking for data repairs.

Predicting Prefix Availability in the Internet.
Abstract—The Border Gateway Protocol (BGP) maintains inter-domain routing information by announcing and withdrawing IP prefixes, possibly resulting in temporary prefix unreachability. Prefix availability observed from different vantage points in the Internet can be lower than standards promised by Service Level Agreements (SLAs). In this paper, we develop a framework for predicting long-term prefix availability, given short-duration prefix information from publicly available BGP routing databases. We compare three prediction models, and find that bagged decision trees perform the best when predicting for long future durations, whereas a simple model works well for short prediction durations. We show that mean time to failure and to recovery outperform past availability in terms of their importance for predicting availability for long durations. We also find that predictability is higher in the year 2009, compared to four years earlier. Our models allow ISPs to adjust BGP routing policies if predicted availability is low, and the models are useful for cloud computing systems, P2P, and VoIP applications.
GDR a system for guided data repair.

ERACER a database approach for statistical inference and data cleaning.

Randomization tests for distinguishing social influence and homophily effects.

Modeling relationship strength in online social networks.

Evaluating Statistical Tests for Within%2DNetwork Classifiers of Relational Data.
Recently a number of modeling techniques have been developed for data mining and machine learning in relational and network domains where the instances are not independent and identically distributed (i.i.d.). These methods specifically exploit the statistical dependencies among instances in order to improve classification accuracy. However, there has been little focus on how these same dependencies affect our ability to draw accurate conclusions about the performance of the models. More specifically, the complex link structure and attribute dependencies in network data violate the assumptions of many conventional statistical tests and make it difficult to use these tests to assess the models in an unbiased manner. In this work, we examine the task of within-network classification and the question of whether two algorithms will learn models which will result in significantly different levels of performance. We show that the commonly-used form of evaluation (paired t-test on overlapping network samples) can result in an unacceptable level of Type I error. Furthermore we show that Type I error increases as (1) the correlation among instances increases and (2) the size of the evaluation set increases (i.e., the proportion of labeled nodes in the network decreases). We propose a method for network cross-validation that combined with paired t-tests produces more acceptable levels of Type I error while still providing reasonable levels of statistical power (i.e., Type II error). 1.
Using Transactional Information to Predict Link Strength in Online Social Networks.
Many scientific fields analyzing and modeling social networks have focused on manually-collected datasets where the friendship links are sparse (due to the costs of collection) but relatively noise-free (i.e. they indicate strong relationships). In online social networks, where the notion of “friendship ” is broader than what would generally be considered in sociological studies, the friendship links are denser but the links contain noisier information (i.e., some weaker relationships). However, the networks also contain additional transactional events among entities (e.g., communication, file transfers) that can be used to infer the true underlying social network. With this aim in mind, we develop a supervised learning approach to predict link strength from transactional information. We formulate this as a link prediction task and compare the utility of attribute-based, topological, and transactional features. We evaluate our approach on public data from the Purdue Facebook network and show that we can accurately predict strong relationships. Moreover, we show that transactional-network features are the most influential features for this task.
Database Support for Probabilistic Attributes and Tuples.
Abstract — The inherent uncertainty of data present in numerous applications such as sensor databases, text annotations, and information retrieval motivate the need to handle imprecise data at the database level. Uncertainty can be at the attribute or tuple level and is present in both continuous and discrete data domains. This paper presents a model for handling arbitrary probabilistic uncertain data (both discrete and continuous) natively at the database level. Our approach leads to a natural and efficient representation for probabilistic data. We develop a model that is consistent with possible worlds semantics and closed under basic relational operators. This is the first model that accurately and efficiently handles both continuous and discrete uncertainty. The model is implemented in a real database system (PostgreSQL) and the effectiveness and efficiency of our approach is validated experimentally. I.
Pseudolikelihood EM for Within%2Dnetwork Relational Learning.
In this work, we study the problem of within-network relational learning and inference, where models are learned on a partially labeled relational dataset and then are applied to predict the classes of unlabeled instance in the same graph. We categorized recent work in statistical relational learning into three alternative approaches for this setting: disjoint learning with disjoint inference, disjoint learning with collective inference, and collective learning with collective inference. Models from each of these categories has been employed previously in different settings, but to our knowledge there has been no systematic comparison of models from all three categories. In this paper, we develop a novel pseudolikelihood EM method that facilitates more general collective learning and collective inference on partially labeled relational networks. We then compare this method to competing methods from the other categories on both synthetic and real-world data. We show that there is a region of performance, when there is a moderate number of labeled examples, where the pseudolikelihood EM approach achieves significantly higher accuracy. 1
Temporal%2DRelational Classifiers for Prediction in Evolving Domains.
Many relational domains contain temporal information and dynamics that are important to model (e.g., social networks, protein networks). However, past work in relational learning has focused primarily on modeling static “snapshots” of the data and has largely ignored the temporal dimension of these data. In this work, we extend relational techniques to temporally-evolving domains and outline a representational framework that is capable of modeling both temporal and relational dependencies in the data. We develop efficient learning and inference techniques within the framework by considering a restricted set of temporalrelational dependencies and using parameter-tying methods to generalize across relationships and entities. More specifically, we model dynamic relational data with a twophase process, first summarizing the temporal-relational information with kernel smoothing, and then moderating attribute dependencies with the summarized relational information. We develop a number of novel temporal-relational models using the framework and then show that the current approaches to modeling static relational data are special cases within the framework. We compare the new models to the competing static relational methods on three real-world datasets and show that the temporal-relational models consistently outperform the relational models that ignore temporal information—achieving significant reductions in error ranging from 15 % to 70%. 1
A Shrinkage Approach for Modeling Non%2Dstationary Relational Autocorrelation.

AI%27s 10 to Watch.

A bias%2Fvariance decomposition for models using collective inference.
Abstract. Bias/variance analysis is a useful tool for investigating the performance of machine learning algorithms. Conventional analysis decomposes loss into errors due to aspects of the learning process, but in relational domains, the inference process used for prediction introduces an additional source of error. Collective inference techniques introduce additional error, both through the use of approximate inference algorithms and through variation in the availability of test-set information. To date, the impact of inference error on model performance has not been investigated. We propose a new bias/variance framework that decomposes loss into errors due to both the learning and inference processes. We evaluate the performance of three relational models on both synthetic and real-world datasets and show that (1) inference can be a significant source of error, and (2) the models exhibit different types of errors as data characteristics are varied.
A bias%2Fvariance decomposition for models using collective inference.
Abstract. Bias/variance analysis is a useful tool for investigating the performance of machine learning algorithms. Conventional analysis decomposes loss into errors due to aspects of the learning process, but in relational domains, the inference process used for prediction introduces an additional source of error. Collective inference techniques introduce additional error, both through the use of approximate inference algorithms and through variation in the availability of test-set information. To date, the impact of inference error on model performance has not been investigated. We propose a new bias/variance framework that decomposes loss into errors due to both the learning and inference processes. We evaluate the performance of three relational models on both synthetic and real-world datasets and show that (1) inference can be a significant source of error, and (2) the models exhibit different types of errors as data characteristics are varied.
Bias%2FVariance Analysis for Relational Domains.

Structure Learning for Statistical Relational Models.

Leveraging Relational Autocorrelation with Latent Group Models.
Abstract. The presence of autocorrelation provides strong motivation for using relational techniques for learning and inference. Autocorrelation is a statistical dependency between the values of the same variable on related entities and is a nearly ubiquitous characteristic of relational data sets. Recent research has explored the use of collective inference techniques to exploit this phenomenon. These techniques achieve significant performance gains by modeling observed correlations among class labels of related instances, but the models fail to capture a frequent cause of autocorrelation—the presence of underlying groups that influence the attributes on a set of entities. We propose a latent group model (LGM) for relational data, which discovers and exploits the hidden structures responsible for the observed autocorrelation among class labels. Modeling the latent group structure improves model performance, increases inference efficiency, and enhances our understanding of the datasets. We evaluate performance on three relational classification tasks and show that LGM outperforms models that ignore latent group structure when there is little known information with which to seed inference.
Using relational knowledge discovery to prevent securities fraud.
We describe an application of relational knowledge discovery to a key regulatory mission of the National Association of Securities Dealers (NASD). NASD is the world’s largest private-sector securities regulator, with responsibility for preventing and discovering misconduct among securities brokers. Our goal was to help focus NASD’s limited regulatory resources on the brokers who are most likely to engage in securities violations. Using statistical relational learning algorithms, we developed models that rank brokers with respect to the probability that they would commit a serious violation of securities regulations in the near future. Our models incorporate organizational relationships among brokers (e.g., past coworker), which domain experts consider important but have not been easily used before now. The learned models were subjected to an extensive evaluation using more than 18 months of data unseen by the model developers and comprising over two person weeks of effort by NASD staff. Model predictions were found to correlate highly with the subjective evaluations of experienced NASD examiners. Furthermore, in all performance measures, our models performed as well as or better than the handcrafted rules that are currently in use at NASD.
Leveraging relational autocorrelation with latent group models.
Abstract. The presence of autocorrelation provides strong motivation for using relational techniques for learning and inference. Autocorrelation is a statistical dependency between the values of the same variable on related entities and is a nearly ubiquitous characteristic of relational data sets. Recent research has explored the use of collective inference techniques to exploit this phenomenon. These techniques achieve significant performance gains by modeling observed correlations among class labels of related instances, but the models fail to capture a frequent cause of autocorrelation—the presence of underlying groups that influence the attributes on a set of entities. We propose a latent group model (LGM) for relational data, which discovers and exploits the hidden structures responsible for the observed autocorrelation among class labels. Modeling the latent group structure improves model performance, increases inference efficiency, and enhances our understanding of the datasets. We evaluate performance on three relational classification tasks and show that LGM outperforms models that ignore latent group structure when there is little known information with which to seed inference.
Dependency Networks for Relational Data.
Instance independence is a critical assumption of traditional machine learning methods contradicted by many relational datasets. For example, in scientific literature datasets there are dependencies among the references of a paper. Recent work on graphical models for relational data has demonstrated significant performance gains for models that exploit the dependencies among instances. In this paper, we present relational dependency networks (RDNs), a new form of graphical model capable of reasoning with such dependencies in a relational setting. We describe the details of RDN models and outline their strengths, most notably the ability to learn and reason with cyclic relational dependencies. We present RDN models learned on a number of real-world datasets, and evaluate the models in a classification context, showing significant performance improvements. In addition, we use synthetic data to evaluate the quality of model learning and inference procedures. 1.
Why collective inference improves relational classification.
Procedures for collective inference make simultaneous statistical judgments about the same variables for a set of related data instances. For example, collective inference could be used to simultaneously classify a set of hyperlinked documents or infer the legitimacy of a set of related financial transactions. Several recent studies indicate that collective inference can significantly reduce classification error when compared with traditional inference techniques. We investigate the underlying mechanisms for this error reduction by reviewing past work on collective inference and characterizing different types of statistical models used for making inference in relational data. We show important differences among these models, and we characterize the necessary and sufficient conditions for reduced classification error based on experiments with real and simulated data.
Simple Estimators for Relational Bayesian Classifiers.
This paper evaluates several modifications of the  Simple Bayesian Classifier to enable estimation  and inference over relational data. The resulting  Relational Bayesian Classifiers are evaluated on  three real-world datasets and compared to a  baseline SBC using no relational information
Avoiding Bias when Aggregating Relational Data with Degree Disparity.
A common characteristic of relational data sets —degree disparity—can lead relational learning algorithms to discover misleading correlations. Degree disparity occurs when the frequency of a relation is correlated with the values of the target variable. In such cases, aggregation functions used by many relational learning algorithms will result in misleading correlations and added complexity in models. We examine this problem through a combination of simulations and experiments. We show how two novel hypothesis testing procedures can adjust for the effects of using aggregation functions in the presence of degree disparity. 1.
Learning relational probability trees.
Classification trees are widely used in the machine learning and data mining communities for modeling propositional data. Recent work has extended this basic paradigm to probability estimation trees. Traditional tree learning algorithms assume that instances in the training data are homogenous and independently distributed. Relational probability trees (RPTs) extend standard probability estimation trees to a relational setting in which data instances are heterogeneous and interdependent. Our algorithm for learning the structure and parameters of an RPT searches over a space of relational features that use aggregation functions (e.g. AVERAGE, MODE, COUNT) to dynamically propositionalize relational data and create binary splits within the RPT. Previous work has identified a number of statistical biases due to characteristics of relational data such as autocorrelation and degree disparity. The RPT algorithm uses a novel form of randomization test to adjust for these biases. On a variety of relational learning tasks, RPTs built using randomization tests are significantly smaller than other models and achieve equivalent, or better, performance. 1.
Exploiting relational structure to understand publication patterns in high%2Denergy physics.
We analyze publication patterns in theoretical high-energy physics using a relational learning approach. We focus on four related areas: understanding and identifying patterns of citations, examining publication patterns at the author level, predicting whether a paper will be accepted by specific journals, and identifying research communities from the citation patterns and paper text. Each of these analyses contributes to an overall understanding of theoretical highenergy physics. 1.
Linkage and Autocorrelation Cause Feature Selection Bias in Relational Learning.
Two common characteristics of relational data  sets --- concentrated linkage and relational autocorrelation  --- can cause learning algorithms to  be strongly biased toward certain features, irrespecti  e of their predicti e power. We identify  these characteristics, define quantitati e measures  of their se erity, and explain how they produce  this bias. We show how linkage and autocorrelation  affect a representati e algorithm for  feature selection by applying the algorithm to  synthetic data and to data drawn from the Internet  Mo ie Database.
Autocorrelation and Linkage Cause Bias in Evaluation of Relational Learners.
Two common characteristics of relational data sets — concentrated linkage and relational auto-correlation — can cause traditional methods of evaluation to greatly overestimate the accuracy of induced models on test sets. We identify these characteristics, define quantitative measures of their severity, and explain how they produce this bias. We show how linkage and autocorrelation affect estimates of model accuracy by applying FOIL to synthetic data and to data drawn from the Internet Movie Database. We show how a modified sampling procedure can eliminate the bias.
